﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FindGreatestLinkedNode.Question;

namespace FindGreatestLinkedNode.Answer
{
    class BobRecursive:IFindNearestGreatestNodeInBinaryTree
    {
        public int? Search(Node root, int k, Node parent)
        {
            if (root == null)
                return null;


            if (root.Data == k)
            {
                var res = root.Data;
                if (parent != null)
                    res = Math.Max(res, parent.Data);

                if (root.LeftChild != null)
                    res = Math.Max(res, root.LeftChild.Data);

                if (root.RightChild != null)
                    res = Math.Max(res, root.RightChild.Data);

                return res;
            }
            else
            {
                int? left = null;
                int? right = null;
                if (root.LeftChild != null)
                {
                    left = Search(root.LeftChild, k, root);
                }
                if (root.RightChild != null)
                {
                    right = Search(root.RightChild, k, root);
                }                   
                

                if (left != null && right == null)
                {
                    return left;
                }


                if (left == null && right != null)
                {
                    return right;
                }
                
                if (left != null && right != null)
                {
                    return Math.Max((int)left, (int)right);
                }
                return null;
            }
        }


        public int? FindNearestGreatestNode(Node root, int k)
        {
            return Search(root, k, null);
        }
    }


}
